﻿#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
#include"Binary.h"
//建树
BNode* StrBinaryTree(BNode* qp,int x)
{
	assert(qp);
	BNode* node = (BNode*)malloc(sizeof(BNode));
	node->left = NULL;
	node->right = NULL;
	node->val = x;
	return node;
}
//前序遍历
void FroOrder(BNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	FroOrder(root->left);
	FroOrder(root->right);
}
//中序遍历
void InOrder(BNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
//后序遍历
void AftOrder(BNode* root)
{
	if (root == NULL)
	{
		return;
	}
	AftOrder(root->left);
	AftOrder(root->right);
	printf("%d ", root->val);
}
//层序遍历
void SeqOrder(BNode* root)
{
	Que qp;
	QueueInit(&qp);
	assert(root);
	if (root)
	{
		QueuePush(&qp, root);
	}
	while (!QueueEmpty(&qp))
	{
		BNode* front = QueueFront(&qp);
		printf("%d ", front->val);
		if (front->left)
		{
			QueuePush(&qp, front->left);
		}
		if (front->right)
		{
			QueuePush(&qp, front->right);
		}
		QueuePop(&qp);
	}
	printf("\n");
	QueueDestroy(&qp);
}
//判断二叉树是否是完全二叉树
bool IsallTree(BNode* root)
{
	Que qp;
	QueueInit(&qp);
	assert(root);
	if (root)
	{
		QueuePush(&qp, root);
	}
	while (!QueueEmpty(&qp))
	{
		BNode* front = QueueFront(&qp);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&qp, front->left);
		QueuePush(&qp, front->right);
		QueuePop(&qp);
	}
	while (!QueueEmpty(&qp))
	{
		BNode* front = QueueFront(&qp);
		QueuePop(&qp);
		if (front != NULL)
		{
			QueueDestroy(&qp);
			return false;
		}
	}
	QueueDestroy(&qp);
	return true;
}
//销毁树
void DestroyTree(BNode* root)
{
	assert(root);
	if (root == NULL)
	{
		return;
	}
	if (root->left)
	{
		DestroyTree(root->left);
	}
	if (root->right)
	{
		DestroyTree(root->right);
	}
	DestroyTree(root);
}
//总节点数
int TreeNode(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeNode(root->left) + TreeNode(root->right) + 1;
}
//叶子数
int TreeLeaf(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left==NULL&& root->right == NULL)
	{
		return 1;
	}
	return TreeLeaf(root->left) + TreeLeaf(root->right);
}
//第K层的叶子数
//int KTreeLeaf(BNode* root, int* k)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	if (*k == 2)
//	{
//		return KTreeLeaf(root->left,k) + KTreeLeaf(root->right,k) + 1;
//	}
//	return kTreeLeaf(root->left, *k - 1) + KTreeLeaf(root->right, *k - 1);
//
//}
//查找val值为x的节点
BNode* FindNode(BNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	BNode* node = NULL;
	if (root->val == x)
	{
		return root;
	}
	node = FindNode(root->left, x);
	if (node)
		return node;
	node = NULL;
	node = FindNode(root->right, x);
	if (node)
		return node;
	return NULL;
}
